import bsTree from "./bsTree3";
import AVLTreeNode from "./01-封装AVLTreeNode";
class AVLTree<T> extends bsTree<T> {
  root: AVLTreeNode<T> | null = null;

  protected createNode(value: T): AVLTreeNode<T> {    
    return new AVLTreeNode<T>(value);
  }
  /**
   *恢复平衡
   * @param root 不平衡的节点
   */
  rebanlance(root: AVLTreeNode<T>) {
    // 获取轴心节点1
    const pivot = root.hightChild!;
    // 获取轴心节点2
    const pivot2 = pivot.hightChild!;

    if (pivot.isLeft && pivot2.isLeft) {
      console.log("左左");
      root.rightRation();
    } else if (pivot.isLeft && pivot2.isRight) {
      console.log("左右");
      pivot.leftRation();
      root.rightRation();
    } else if (pivot.isRight && pivot2.isLeft) {
      console.log("右左");
      pivot.rightRation();
      root.leftRation();
    } else if (pivot.isRight && pivot2.isRight) {
      console.log("右右");
      root.leftRation();
    }

    // 判断返回的piovt没有父节点（那就是说失衡的点就是定点）
    if(!pivot.parent){
      this.root = pivot;
    }
  }
}

const avlTree = new AVLTree<number>();

// 左左-且失衡点是定点
avlTree.insert(10);
avlTree.insert(9);
avlTree.insert(8);
avlTree.print();
avlTree.rebanlance(avlTree.search(10) as AVLTreeNode<number>);
avlTree.print();

//        10       
//     ┌───┘
//     9
//   ┌─┘
//   8
// 左左
//     9
//   ┌─┴─┐
//   8  10

// 左左
// avlTree.insert(11);
// avlTree.insert(10);
// avlTree.insert(9);
// avlTree.insert(8);
// avlTree.print();
// avlTree.rebanlance(avlTree.search(10) as AVLTreeNode<number>);
// avlTree.print();
//                11
//         ┌───────┘
//        10
//     ┌───┘
//     9
//   ┌─┘
//   8
// 左左
//        11
//     ┌───┘
//     9
//   ┌─┴─┐
//   8  10

// 右右
// avlTree.insert(10);
// avlTree.insert(11);
// avlTree.insert(12);
// avlTree.insert(13);
// avlTree.print();
// avlTree.rebanlance(avlTree.search(11) as AVLTreeNode<number>);
// avlTree.print();
//                10
//                 └───────┐
//                        11
//                         └───┐
//                            12
//                             └─┐
//                              13
// 右右
//        10
//         └───┐
//            12
//           ┌─┴─┐
//          11  13

// 左右
// avlTree.insert(10);
// avlTree.insert(9);
// avlTree.insert(7);
// avlTree.insert(8);
// avlTree.print();
// avlTree.rebanlance(avlTree.search(9) as AVLTreeNode<number>);
// avlTree.print();
//                10
//         ┌───────┘
//         9
//     ┌───┘
//     7
//     └─┐
//       8
// 左右
//        10
//     ┌───┘
//     8
//   ┌─┴─┐
//   7   9

// 右左
// avlTree.insert(10);
// avlTree.insert(11);
// avlTree.insert(12);
// avlTree.insert(11.5);
// avlTree.print();
// avlTree.rebanlance(avlTree.search(11) as AVLTreeNode<number>);
// avlTree.print();

//                10
//                 └───────┐
//                        11
//                         └───┐
//                            12
//                           ┌─┘
//                         11.5
// 右左
//        10
//         └───┐
//           11.5
//           ┌─┴─┐
//          11  12